package algorithm;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-03-22
 * Time：23:29
 */


public class KMP {

    public  static void creatNext(int []array,String str) {
        int sz=array.length;
        int i=2;
        array[0]=-1;
        array[1]=0;
        int k=array[1];
        while (i<sz) {
            if (k == -1 || (str.charAt(i - 1) == str.charAt(k))) {
                array[i] = k + 1;
                k++;
                i++;
            } else {
                int tmp = i;
                tmp = array[tmp - 1];
                k = array[tmp];
            }
        }
    }

    public static int  KMPFunc(String s1,String s2) {
        if (s1==null || s2==null) {
            return -1;
        }
        int sz1=s1.length();
        int sz2=s2.length();
        if (sz1==0 || sz2==0) {
            return -1;
        }
        int i=0,j=0;

        int []next =new int[sz2];


        creatNext(next,s2);
        int count=0;

        while (i<sz1 && j<sz2) {

            if (j==-1||s1.charAt(i)==s2.charAt(j) ) {
                j++;
            } else {
                j=next[j];
            }

            i++;
            count++;
        }

        System.out.println(count);

        if (j==sz2) {
            return i-j;
        }

        return -1;
    }

    public static void main(String[] args) {


        System.out.println(KMPFunc("ababcabcdacac", "abcd"));

        System.out.println();

    }
}
